#include <bits/stdc++.h>

#define in read()

using namespace std;

typedef long long ll;

int read(){int x = 0,sgn = 1;char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;for(;isdigit(ch);ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48); return x * sgn;}

const int N = 5e5+10;
const int inf = 0x3f3f3f3f;

int n,a[N],m;

namespace st{
	struct node{int mx,mx_,mxx,cnt;ll s;}val[N<<2];
	struct lztag{int ad1,ad2,ad3,ad4;}lz[N<<2];
	
	node operator + (node a,node b){
		node c; c.s = a.s + b.s; c.mx_ = max(a.mx_,b.mx_); c.mx = max(a.mx,b.mx);
		if(a.mx == b.mx){c.cnt = a.cnt + b.cnt; c.mxx = max(a.mxx,b.mxx);}
		else if(a.mx > b.mx){c.cnt = a.cnt; c.mxx = max(a.mxx,b.mx);}
		else{c.cnt = b.cnt; c.mxx = max(a.mx,b.mxx);} return c;
	}

	void build(int o = 1,int l = 1,int r = n){
		if(l == r) return val[o] = (node){a[l],a[l],-inf,1,a[l]},void(); int mid = l + r >> 1; build(o << 1,l,mid); build(o << 1 | 1,mid + 1,r); val[o] = val[o << 1] + val[o << 1 | 1];
	}

	void add(int o,int d1,int d2,int d3,int d4,int l,int r){
		val[o].s += (ll) d1 * val[o].cnt + (ll) d3 * (r - l + 1 - val[o].cnt);
		val[o].mx_ = max(val[o].mx_,val[o].mx + d2); lz[o].ad2 = max(lz[o].ad2,lz[o].ad1 + d2);
		val[o].mx += d1; lz[o].ad1 += d1; lz[o].ad4 = max(lz[o].ad4,lz[o].ad3 + d4);
		lz[o].ad3 += d3; if(val[o].mxx > -inf) val[o].mxx += d3;
	}

	void pushdown(int o,int l,int r){
		int mid = l + r >> 1; int mmx = max(val[o << 1].mx , val[o << 1 | 1].mx);
		if(val[o << 1].mx == mmx) add(o << 1,lz[o].ad1,lz[o].ad2,lz[o].ad3,lz[o].ad4,l,mid);
		else add(o << 1,lz[o].ad3,lz[o].ad4,lz[o].ad3,lz[o].ad4,l,mid);
		if(val[o << 1 | 1].mx == mmx) add(o << 1 | 1,lz[o].ad1,lz[o].ad2,lz[o].ad3,lz[o].ad4,mid + 1,r);
		else add(o << 1 | 1,lz[o].ad3,lz[o].ad4,lz[o].ad3,lz[o].ad4,mid + 1,r);
		lz[o].ad1 = lz[o].ad2 = lz[o].ad3 = lz[o].ad4 = 0;
	}
	
	void upd(int xl,int xr,int k,int o = 1,int l = 1,int r = n){//all add k
		if(xl == l && xr == r) return add(o,k,k,k,k,l,r); int mid = l + r >> 1;pushdown(o,l,r); if(xr <= mid) upd(xl,xr,k,o<<1,l,mid);
		else if(xl > mid) upd(xl,xr,k,o<<1|1,mid+1,r); else upd(xl,mid,k,o<<1,l,mid),upd(mid+1,xr,k,o<<1|1,mid+1,r);
		val[o] = val[o << 1] + val[o << 1 | 1];
	}

	void upd1(int xl,int xr,int k,int o = 1,int l = 1,int r = n){//get mn k
		if(val[o].mx <= k) return; int mid = l + r >> 1; 
		if(xl == l && xr == r){
			if(val[o].mxx < k) add(o,k - val[o].mx,k - val[o].mx,0,0,l,r);
			else if(l ^ r) pushdown(o,l,r),upd1(xl,mid,k,o<<1,l,mid), upd1(mid + 1,xr,k,o<<1|1,mid+1,r),val[o] = val[o << 1] + val[o << 1 | 1];
			return;
		}pushdown(o,l,r); if(xr <= mid) upd1(xl,xr,k,o<<1,l,mid); else if(xl > mid) upd1(xl,xr,k,o<<1|1,mid+1,r); else upd1(xl,mid,k,o<<1,l,mid),upd1(mid + 1,xr,k,o<<1|1,mid+1,r);val[o] = val[o << 1] + val[o << 1 | 1];
	}

	ll qsum(int xl,int xr,int o = 1,int l = 1,int r = n){
		if(xl == l && xr == r) return val[o].s; int mid = l + r >> 1; pushdown(o,l,r);
		if(xr <= mid) return qsum(xl,xr,o<<1,l,mid); else if(xl > mid) return qsum(xl,xr,o<<1|1,mid+1,r);
		else return qsum(xl,mid,o<<1,l,mid) + qsum(mid + 1,xr,o<<1|1,mid+1,r);
	}

	int qmx(int xl,int xr,int o = 1,int l = 1,int r = n){
		if(xl == l && xr == r) return val[o].mx; int mid = l + r >> 1; pushdown(o,l,r);
		if(xr <= mid) return qmx(xl,xr,o<<1,l,mid); else if(xl > mid) return qmx(xl,xr,o<<1|1,mid+1,r);
		else return max(qmx(xl,mid,o<<1,l,mid) , qmx(mid + 1,xr,o << 1 | 1,mid + 1,r));
	}

	int qbmx(int xl,int xr,int o = 1,int l = 1,int r = n){
		if(xl == l && xr == r) return val[o].mx_; int mid = l + r >> 1; pushdown(o,l,r);
		if(xr <= mid) return qbmx(xl,xr,o<<1,l,mid); else if(xl > mid) return qbmx(xl,xr,o<<1|1,mid + 1,r);
		else return max(qbmx(xl,mid,o<<1,l,mid) , qbmx(mid + 1,xr,o<<1|1,mid + 1,r));
	}
	
}//segtree

using namespace st;

int main(){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin); freopen("P6242.out","w",stdout);
#endif
	n = in; m = in; for(int i = 1;i <= n;i++) a[i] = in; build();
	while(m--){
		int op,l,r,v; op = in,l = in,r = in; if(op <= 2) v = in;
		if(op == 1) upd(l,r,v); else if(op == 2) upd1(l,r,v); else if(op == 3) printf("%lld\n",qsum(l,r)); else if(op == 4) printf("%d\n",qmx(l,r)); else printf("%d\n",qbmx(l,r));
	}
	return 0;
}
